package sort;

/**
 * 选择排序法 O(N^2)
 * 每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。
 */
public class SelectionSort {

    //直接选择排序法
    public static void selectionSort(int[] arr) {
        // i表示无序区间的起始位置
        for(int i = 0; i < arr.length - 1; i++){
            int min = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            if(min != i){
                swap(arr, i, min);
            }
        }
    }

    //双向选择排序法
    public static void selectionSortOP(int[] arr) {
        //无序区间的起始位置和终了位置
        int prev = 0;
        int tail = arr.length - 1;
        while(prev < tail) {
            int min = prev, max = prev;
            for(int i = prev + 1; i <= tail; i++){
                if(arr[min] > arr[i]){
                    min = i;
                }
                if(arr[max] < arr[i]){
                    max = i;
                }
            }
            //把最小值换到无序区间的前面
            swap(arr, prev, min);
            //假如刚好max在prev的位置时，经过交换后max到了min的位置
            if(max == prev){
                max = min;
            }
            swap(arr, tail, max);
            prev ++;
            tail --;
        }
    }

    //交换索引位置的元素值
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
    }
}
